/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package utils;

import types.ISudokuMatrix;
import types.SudokuMatrix;

/**
 *
 * @author ali
 */
public class SudokuSolver {

    /**
     * returns a [10]*[10] solved sudoku board
     *
     * @param a [10][10] sudoku board
     * @return
     */
    public static ISudokuMatrix solveSudoku(ISudokuMatrix board) {

        Integer[][] array = new Integer[9][9];

        ISudokuMatrix solveds = new SudokuMatrix(array);
        int[][] matrix = new int[9][9];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                matrix[i][j] = (Integer) board.getElementAt(i, j);
            }
        }

        writeMatrix(matrix);
        if (solve(0, 0, matrix)) {
            writeMatrix(matrix);


            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    solveds.insertElementAt((Integer) matrix[i][j], i, j);
                }
            }

            return solveds;
        } else {
            return null;
        }

    }

    private static boolean solve(int i, int j, int[][] cells) {
        if (i == 9) {
            i = 0;
            if (++j == 9) {
                return true;
            }
        }
        if (cells[i][j] != 0) // skip filled cells
        {
            return solve(i + 1, j, cells);
        }

        for (int val = 1; val <= 9; ++val) {
            if (legal(i, j, val, cells)) {
                cells[i][j] = val;
                if (solve(i + 1, j, cells)) {
                    return true;
                }
            }
        }
        cells[i][j] = 0; // reset on backtrack
        return false;
    }

    private static boolean legal(int i, int j, int val, int[][] cells) {
        for (int k = 0; k < 9; ++k) // row
        {
            if (val == cells[k][j]) {
                return false;
            }
        }

        for (int k = 0; k < 9; ++k) // col
        {
            if (val == cells[i][k]) {
                return false;
            }
        }

        int boxRowOffset = (i / 3) * 3;
        int boxColOffset = (j / 3) * 3;
        for (int k = 0; k < 3; ++k) // box
        {
            for (int m = 0; m < 3; ++m) {
                if (val == cells[boxRowOffset + k][boxColOffset + m]) {
                    return false;
                }
            }
        }

        return true; // no violations, so it's legal
    }

    private static int[][] parseProblem(String[] args) {
        int[][] problem = new int[9][9]; // default 0 vals
        for (int n = 0; n < args.length; ++n) {
            int i = Integer.parseInt(args[n].substring(0, 1));
            int j = Integer.parseInt(args[n].substring(1, 2));
            int val = Integer.parseInt(args[n].substring(2, 3));
            problem[i][j] = val;
        }
        return problem;
    }

    static private void writeMatrix(int[][] solution) {
        for (int i = 0; i < 9; ++i) {
            if (i % 3 == 0) {
                System.out.println(" -----------------------");
            }
            for (int j = 0; j < 9; ++j) {
                if (j % 3 == 0) {
                    System.out.print("| ");
                }
                System.out.print(solution[i][j] == 0
                        ? " "
                        : Integer.toString(solution[i][j]));

                System.out.print(' ');
            }
            System.out.println("|");
        }
        System.out.println(" -----------------------");
    }
}



